Q: In postorder traversal of binary tree right subtree is traversed before visiting root.
Solution: Post-order method of traversing involves – i) Traverse left subtree in post-order, ii) Traverse right subtree in post-order, iii) visit the root.
Q: What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order.
Solution: 5 binary trees are possible and they are,
Q: The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be ________
Solution: The last, second last nodes visited in post-order traversal are root and it’s right child respectively. Option T Q R S O P can’t be a pre-order traversal, because nodes O, P are visited after the nodes Q, R, S. Option T O Q R P S, can’t be valid, because the pre-order sequence given in option T O Q R P S and given post-order traversal creates a tree with node T as root and node O as left subtree. Option T Q O P S R is valid. Option T Q O S P R is not valid as node P is visited after visiting node S.
Q: A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, 75. Which one of the following is a valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40 and 75?
Solution: The binary tree contains values 7, 8, 13, 26, 35, 40, 70, 75. The given pre-order sequence is 35, 13, 7, 8, 26, 70, 40 and 75. So, the binary search tree formed is postorder-traversal-questions-answers-q4 Thus post-order sequence for the tree is 8, 7, 26, 13, 40, 75, 70 and 35.
Q: Which of the following pair’s traversals on a binary tree can build the tree uniquely?
Solution: A binary tree can uniquely be created by post-order and in-order traversals.
Q: A full binary tree can be generated using ______
Solution: Every node in a full binary tree has either 0 or 2 children. A binary tree can be generated by two traversals if one of them is in-order. But, we can generate a full binary tree using post-order and pre-order traversals.
Q: The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is ______
Solution: The tree with only one node has post-order and pre-order traversals equal.
Q: The steps for finding post-order traversal are traverse the right subtree, traverse the left subtree or visit the current node.
Solution: Left subtree is traversed first in post-order traversal, then the right subtree is traversed and then the output current node.
Q: The pre-order and in-order are traversals of a binary tree are T M L N P O Q and L M N T O P Q. Which of following is post-order traversal of the tree?
Solution: The tree generated by using given pre-order and in-order traversal is postorder-traversal-questions-answers-q9 Thus, L N M O Q P T will be the post-order traversal.
Q: For a binary tree the first node visited in in-order and post-order traversal is same.
Solution: Consider a binary tree, postorder-traversal-questions-answers-q10 Its in-order traversal – 13 14 16 19 Its post-order traversal- 14 13 19 16. Here the first node visited is not same.
| You Have Score | /10 |